package com.xx.springboot.DataStructure.LeetCode.BST;

/**
     将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。

     本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

     示例:

     给定有序数组: [-10,-3,0,5,9],

     一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：

          0
         / \
       -3   9
       /   /
     -10  5
 */
public class sortedArrayToBST {
    public TreeNode sortedArrayToBST(int[] nums) {

        if(nums.length == 0)
            return null;

        int index = nums.length % 2 == 1 ? (nums.length - 1) / 2 : nums.length / 2;

        TreeNode root = new TreeNode(nums[index]);
        for (int i = 0 ; i < nums.length ; i ++) {
            add(root, nums[i]);
        }
        return root;
    }

    public TreeNode add(TreeNode root, int e){
        if (root == null) {
            return new TreeNode(e);
        }

        if(e > root.val)
            root.right = add(root.right, e);
        if(e < root.val)
            root.left = add(root.left, e);
        return root;
    }
}
